class Solution {
    public List<String> letterCombinations(String digits) {
        /**
        2: abc
        3: def
        4: ghi
        5: jkl
        6: mno
        7: pqrs
        8: tuv
        9: wxyz
         */
        ans = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return ans;
        }
        cache = new HashMap<>();
        cache.put('2', new String[]{"a", "b", "c"});
        cache.put('3', new String[]{"d", "e", "f"});
        cache.put('4', new String[]{"g", "h", "i"});
        cache.put('5', new String[]{"j", "k", "l"});
        cache.put('6', new String[]{"m", "n", "o"});
        cache.put('7', new String[]{"p", "q", "r", "s"});
        cache.put('8', new String[]{"t", "u", "v"});
        cache.put('9', new String[]{"w", "x", "y", "z"});
        ansItem = new StringBuilder();
        getStr(digits, 0);
        return ans;

    }
    private void getStr(String digits, int index) {
        if (index == digits.length()) {
            ans.add(ansItem.toString());
            return;
        }
        for (String s : cache.get(digits.charAt(index))) {
            ansItem.append(s);
            getStr(digits, index + 1);
            ansItem.deleteCharAt(ansItem.length() - 1);
        }
    }

    private List<String> ans;
    private StringBuilder ansItem;
    Map<Character, String[]> cache;
}
